package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序:
 *  1.思想：
 *      1.1.计数排序，是桶排序的一个特例
 *      1.2.假如全省有100万考生参加考试，满分是750。如何实现根据考生考试成绩进行排名
 *      1.3.实现思路：
 *          1.3.1.根据桶排序原理，以及考试分数范围：0-750。可以分751个桶
 *          1.3.2.每个桶用于存放对应分数的考生数量。比如a[0]，表示0分的考生数量
 *          1.3.3.这里通过数组来代表桶
 *          1.3.4.扫描待排序数组array[n]，通过桶（计数数组）count[max-min]，对每个array[n]
 *          中出现的元素，进行计数
 *          1.3.5.扫描计数数组count[max-min]，还原数组array[n]。排序结束
 *
 *  2.时间复杂度：
 *      O(n)
 *  3.空间复杂度：
 *      O(m)：m是桶的个数
 */
public class CountingSort {
    public static void main(String[] args) {
        // 1.定义待排序数组(这里假设分数范围：0-20)
        Integer[] array = {1,6,3,4,2,5,9,8,10,7,11,20,17,16,15,18,19,2,3,1,9,8,6,1,20};
        int n = array.length;
        System.out.println("1.待排序数组元素个数：" + n +"，元素内容：" + Arrays.asList(array));

        // 2.定义计数数组
        Integer[] count = new Integer[21];
        for (int i = 0; i < count.length; i++) {
            count[i] = 0;
        }

        // 3.扫描待排序数组array[n]，通过桶（计数数组）count[max-min]，对每个array[n]中出现的元素，进行计数
        for(int i = 0; i < array.length; i++){
            count[array[i]] ++;
        }

        System.out.println("2.计数数组元素个数：" + count.length +"，元素内容：" + Arrays.asList(count));

        // 4.扫描计数数组count[max-min]，还原数组array[n]。排序结束
        Integer[] sortResult = new Integer[array.length];
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            if(count[i] > 0){
                for (int j = 0; j < count[i]; j++) {
                    sortResult[k++] = i;
                }
            }

        }

        System.out.println("3.排序后数组元素个数：" + n +"，元素内容：" + Arrays.asList(sortResult));

    }
}
